﻿#pragma once
#include <unordered_map>

using namespace std;

template<class T>
class DoubledLinkedList;

template<class T>
class DoubledLinkedListNode
{
public:
    DoubledLinkedListNode(T t);
    T getValue();
    DoubledLinkedList<T>* getLinkedList();
    void bindLinkedList(DoubledLinkedList<T>* list);

public:
    DoubledLinkedListNode* prev;
    DoubledLinkedListNode* next;

private:
    T value;
    DoubledLinkedList<T>* linkedList;
};


template<class T>
class DoubledLinkedList
{
public:
    DoubledLinkedList();

    /**
     * 在双向链表尾部追加一个节点
     */
    void add(DoubledLinkedListNode<T>* node);

    /**
     * 在双向链表的prevNode后面插入一个节点
     */
    void insert(DoubledLinkedListNode<T>* prevNode, DoubledLinkedListNode<T>* node);

    void remove(DoubledLinkedListNode<T>* node);

    /**
     * 设置双向链表的新头结点
     */
    void setHead(DoubledLinkedListNode<T>* node);
    bool empty();
    DoubledLinkedListNode<T>* getHead();
    DoubledLinkedListNode<T>* getTrail();

private:
    DoubledLinkedListNode<T>* head;
    DoubledLinkedListNode<T>* trail;
};

template<class K, class V>
class LFUCache
{
public:
    LFUCache(int capacity);
    void set(K key, V value);
    V get(K key);
    bool exists(K key);

private:
    /**
     * 原来的节点，由于频次发生了变化，故需要将节点移动到目标频次的桶
     */
    void changeFreqBucket(DoubledLinkedListNode<K>* existNode, int freq);

private:
    int capacity;
    unordered_map<K, V> keyToValueMap;
    unordered_map<K, int> keyToFreqMap;

    /**
     * key对应的每个频次桶内的双向链表的具体节点
     */
    unordered_map<K, DoubledLinkedListNode<K>*> keyToNodeMap;
    DoubledLinkedList<DoubledLinkedList<K>*>* buckets;

    /**
     * 每个频次对应的双向链表桶的节点
     */
    unordered_map<int, DoubledLinkedListNode<DoubledLinkedList<K>*>*> freqBucketMap;
};